package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname BestTimetoBuyandSellStockiii
 * @Description Leetcode 123 买卖股票的最佳时机 |||  困难 动态规划
 * @Date 2021/10/11 21:18
 * @Version 1.0
 */
public class BestTimetoBuyandSellStockiii {

    /**
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;

        int[][][] dp = new int[len][2][3];

        //初始化

        dp[0][0][0] = 0;
        dp[0][1][0] = -prices[0];
        dp[0][1][1] = Integer.MIN_VALUE / 2;
        dp[0][1][2] = Integer.MIN_VALUE / 2;

        //关键如何理解状态转移的
        for (int i = 1; i < len; i++) {

            //第i天不持有股票 且没有销售
            dp[i][0][0] = 0;
            //当天结束后不持有股票，且已经卖出过一次 1.当天卖的,那么前一天持有且没有卖过股票 2.之前卖的 前一天结束之后不持有股票，已经卖了一次
            dp[i][0][1] = Math.max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1]);
            //当天结束，不持有股票，且已经卖出过股票两次 1.当天卖的 2.前一天结束时候已经卖了
            dp[i][0][2] = Math.max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2]);
            //当天结束持有股票，之前没有卖过股票 1.当天买的，且之前不持有股票，且没有卖出过股票 2.之前就持有股票，且没有卖过股票
            dp[i][1][0] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);
            //第i天结束后持有股票，且已经卖过一次 1.当天买的股票，事先已经卖过一次股票且i-1天结束不持有股票 2.
            dp[i][1][1] = Math.max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1]);
            //第i天持有股票，且当天结束后持有股票且已经卖了两次股票
            dp[i][1][2] = Integer.MIN_VALUE / 2;


        }


        return Math.max(Math.max(dp[len - 1][0][1], dp[len - 1][0][2]), 0);
    }
}
